/*
https://leetcode-cn.com/problems/delete-operation-for-two-strings/solution/liang-ge-zi-fu-chuan-de-shan-chu-cao-zuo-14uw/
 */
public class Solution583 {
    public int minDistance(String word1, String word2) {
        int n=word1.length(),m=word2.length();
        int[][] f=new int[n+5][m+5];
        for (int i=1;i<=n;i++){
            char c1=word1.charAt(i-1);
            for (int j=1;j<=m;j++){
                char c2=word2.charAt(j-1);
                if (c1==c2){
                    f[i][j]=f[i-1][j-1]+1;
                }else{
                    f[i][j]=Math.max(f[i-1][j],f[i][j-1]);
                }
            }
        }
        return n+m-2*f[n][m];
    }

    public static void main(String[] args) {
        System.out.println(new Solution583().minDistance("sea","eat"));
    }
}
